package com.melo;

import java.awt.*;
import java.util.ArrayList;
import java.util.List;

/**
 * @author lichunlong lcl253137@alibaba-inc.com
 * @desc 回溯算法: 马踏棋盘小游戏
 * @date 2025-06-12
 */
public class HorseStepChessboard {

    /**
     * 棋盘的列数
     */
    public static final int CHESSBOARD_COLUMN_SIZE = 8;

    /**
     * 棋盘的行数
     */
    public static final int CHESSBOARD_LINE_SIZE = 8;

    /**
     * 标记棋盘的各个位置是否被访问过
     * false: 表示没有访问过; true: 表示已经访问过
     */
    public boolean[][] chessboardVisitedPointArr;

    /**
     * 游戏是否完成的标识
     * false: 未完成; true: 已完成
     */
    private static boolean finishFlag;

    public void traversalChessboard(int[][] chessboardArr, int currentRow, int currentColumn, int currentStep) {
        // 标记该位置为马儿走的第几步
        chessboardArr[currentRow][currentColumn] = currentStep;
        // 标记该位置已访问
        chessboardVisitedPointArr[currentRow][currentColumn] = true;

        // 获取当前位置可以走的下一个位置的集合
        List<Point> nextChessboardPointList = calNextChessboardPoint(new Point(currentColumn, currentRow));
        // 提升效率: 对下一步的集合数量倒序排序, 减少回溯次数
        nextChessboardPointList.sort(new ChessboardPointComparator());

        while (!nextChessboardPointList.isEmpty()) {
            // 取出下一个可以走的位置
            Point nextChessboardPoint = nextChessboardPointList.remove(0);
            if (!chessboardVisitedPointArr[nextChessboardPoint.y][nextChessboardPoint.x]) {
                // 该点还没有被访问过
                traversalChessboard(chessboardArr, nextChessboardPoint.y, nextChessboardPoint.x, currentStep + 1);
            }
        }

        // 判断马儿是否完成了任务，比较step和应该走的步数，如果
        if (currentStep < CHESSBOARD_COLUMN_SIZE * CHESSBOARD_LINE_SIZE && !finishFlag) {
            // 没有达到数量，则没有完成任务，将整个棋盘置0
            chessboardArr[currentRow][currentColumn] = 0;
            chessboardVisitedPointArr[currentRow][currentColumn] = false;
        } else {
            finishFlag = true;
        }
    }

    /**
     * 计算马走日下个位置的方法
     *
     * @param currentChessboardPoint 马儿当前位置
     * @return 马儿下一个位置的集合
     */
    public static List<Point> calNextChessboardPoint(Point currentChessboardPoint) {
        List<Point> nextChessboardPointList = new ArrayList<>();
        Point tempPoint = new Point();
        /*
         * 马走日的方式1: 先向左走2步, 再向上走1步
         */
        if ((tempPoint.x = currentChessboardPoint.x - 2) >= 0 && (tempPoint.y = currentChessboardPoint.y - 1) >= 0) {
            nextChessboardPointList.add(new Point(tempPoint));
        }
        /*
         * 马走日的方式2: 先向右走2步, 再向上走1步
         */
        if ((tempPoint.x = currentChessboardPoint.x + 2) < CHESSBOARD_COLUMN_SIZE && (tempPoint.y = currentChessboardPoint.y - 1) >= 0) {
            nextChessboardPointList.add(new Point(tempPoint));
        }
        /*
         * 马走日的方式3: 先向左走1步, 再向上走2步
         */
        if ((tempPoint.x = currentChessboardPoint.x - 1) >= 0 && (tempPoint.y = currentChessboardPoint.y - 2) >= 0) {
            nextChessboardPointList.add(new Point(tempPoint));
        }
        /*
         * 马走日的方式4: 先向右走1步, 再向上走2步
         */
        if ((tempPoint.x = currentChessboardPoint.x + 1) < CHESSBOARD_COLUMN_SIZE && (tempPoint.y = currentChessboardPoint.y - 2) >= 0) {
            nextChessboardPointList.add(new Point(tempPoint));
        }

        /*
         * 马走日的方式5: 先向左走2步, 再向下走1步
         */
        if ((tempPoint.x = currentChessboardPoint.x - 2) >= 0 && (tempPoint.y = currentChessboardPoint.y + 1) < CHESSBOARD_LINE_SIZE) {
            nextChessboardPointList.add(new Point(tempPoint));
        }
        /*
         * 马走日的方式6: 先向右走2步, 再向下走1步
         */
        if ((tempPoint.x = currentChessboardPoint.x + 2) < CHESSBOARD_COLUMN_SIZE && (tempPoint.y = currentChessboardPoint.y + 1) < CHESSBOARD_LINE_SIZE) {
            nextChessboardPointList.add(new Point(tempPoint));
        }
        /*
         * 马走日的方式7: 先向左走1步, 再向下走2步
         */
        if ((tempPoint.x = currentChessboardPoint.x - 1) >= 0 && (tempPoint.y = currentChessboardPoint.y + 2) < CHESSBOARD_LINE_SIZE) {
            nextChessboardPointList.add(new Point(tempPoint));
        }
        /*
         * 马走日的方式8: 先向右走1步, 再向下走2步
         */
        if ((tempPoint.x = currentChessboardPoint.x + 1) < CHESSBOARD_COLUMN_SIZE && (tempPoint.y = currentChessboardPoint.y + 2) < CHESSBOARD_LINE_SIZE) {
            nextChessboardPointList.add(new Point(tempPoint));
        }

        return nextChessboardPointList;
    }

    /**
     * 打印棋盘
     *
     * @param chessboardArr 棋盘
     */
    public void showChessboard(int[][] chessboardArr) {
        for (int[] chessboardLineArr : chessboardArr) {
            for (int chessboardRowArr : chessboardLineArr) {
                System.out.print(chessboardRowArr + "\t");
            }
            System.out.println();
        }
    }
}
